package datastructure.sort;


/**
 * 排序算法
 *      冒泡排序:
 *          依次比较相邻元素的值, 若发现前一个元素比后一个元素大则交换, 使值较大的元素逐渐从前移向后部
 *      选择排序:
 *          使用一个辅助的变量表示最值对应的下标(记录待排序序列最值的位置, 初始值是待排序序列的第一个下标值),
 *          使最值和待排序序列中的元素依次进行比较, 得到待排序序列的最值下标, 最后最值的元素和待排序序列的第一个元素进行位置交换
 *          相比于冒泡排序, 交换的次数少了, 所以时间也比冒泡排序少, 但是时间复杂度是一样的
 *          选择排序的选择指的是每趟排序要选出最值(最大或者最小)元素进行位置交换
 *      插入排序:
 *          把所有的元素分为两组, 已经排序的和未排序的
 *          从无序表中依次取出第一个元素插入到有序表(待排序序列的前面部分)的指定位置
 *          寻找插入的指定位置是对有序表进行逆序遍历, 把待插入的元素和有序表的元素依次比较, 把有序表的每一个元素右移, 直到找到插入的位置
 *      希尔排序
 *          也是一种插入排序, 缩小增量排序
 *              (依次遍历待排序列表中的元素, 每个元素都需要反序从后往前遍历查找到插入的位置)
 *          基本思想
 *              把待排序数组按下标的增量进行分组, 对每组使用直接插入排序算法排序
 *                  (增量指的是步长, 也就是划分一组元素的间隔, 也就是分组的组数, 初始值是int gap=arr.length/2)
 *              随着增量逐渐减少, 每组包含的元素越来越多
 *              当增量减至1时, 整个数组被分为一组, 算法结束
 *          核心:
 *              为了减少寻找插入位置的时候有序表中元素后移的次数, 提高效率(无需大量移动操作就能完成数组的排序)
 *          注意
 *              1 希尔排序是为了减少寻找插入位置的时候有序表中元素后移的次数, 提高效率
 *                  (无需大量移动操作就能完成数组的排序)
 *              2 插入的时候分为交换法和移动法两种实现方式, 交换法的效率低, 希尔排序使用移位法实现插入效率才高(一般使用移位法)
 *      快速排序
 *          对冒泡排序的一种改进(使用递归 + 双指针 + 临时变量进行交换)
 *          基本思想
 *              选择一个基准元素, 可以是待排序数组的第一个元素、最后一个元素或者中间位置的元素(选择最后一个比较简单)
 *              通过一趟排序将待排序的数组分割成两部分
 *              在划分数组时，将比基准元素小的元素放在左子数组，将比基准元素大的元素放在右子数组
 *                  使用左右双指针交替比较移动
 *                      1 从后往前遍历, 如果当前元素大于基准数据就让high减1,如果小于基准数据就将high位置的值赋值给low位置
 *                      2 再从前往后遍历, 如果当前元素小于基准数据就让low加1,如果大于基准数据就将low位置的值赋值给high位置的值
 *                      3 依次往复进行, 直到low=high结束循环, 此时low或high的下标就是基准数据在该数组中的最终排序位置
 *              然后再按此方法对左右子数组分别进行快速排序(整个排序过程可以递归进行)
 *          核心:
 *              每一趟排序都把待排序数组分割成两部分, 并且都会把基准元素放在最后正确的排序位置
 *      归并排序
 *          分治策略(使用递归 + 双指针 + 辅助数组插入), 时间复杂度为 O(nlogn)
 *          基本思想
 *              1 使用递归实现, 先把数组递归分成左右子数组, 回溯的时候再排序合并子数组
 *              2 合并两个相邻有序子数组, 需要使用双指针和一个临时的数组空间来合两个子数组
 *          注意
 *              快速排序和归并排序都使用了分治和递归
 *              但是快速排序在递归之前排序(分成两部分的时候排序 先排序后递归), 归并排序是在递归回溯的时候进行排序(先递归后排序)
 *              归并排序的缺点是需要额外的数组空间
 *      基数排序
 *          通过键值的个位的值, 将要排序的元素分配至某些桶中, 达到排序的作用
 *          效率高的稳定性排序法(桶排序的扩展)
 *          基本思想
 *              将整数按位数切割成不同的数字, 然后按每个位数分别比较
 *          基数排序的说明
 *              1 空间换时间的方式, 占用内存很大, 对海量数据排序时, 容易造成 OutOfMemoryError
 *              2 有负数的数组, 我们不用基数排序来进行排序
 * 排序的稳定性
 *      概念
 *          数组arr中有若干元素, 其中A元素和B元素相等, 并且A元素在B元素前面,
 *          如果使用某种排序算法排序后, 能够保证A元素依然在B元素的前面, 可以说这个该算法是稳定的
 *      意义
 *          对多次排序的数据具有意义
 *      常见排序算法的稳定性
 *          冒泡排序, 插入排序, 归并排序是稳定的
 *          选择排序, 希尔排序, 快速排序是不稳定的
 *
 *
 */
public class SortMain {
}
